Многочлен над конечным полем

Многочленом $f(x)$ над конечным полем $\mathbb {F} _{q}$ называется формальная сумма вида

f(x)=f_{0}+f_{1}x+\ldots +f_{m}x^{m},\quad f_{i}\in \mathbb {F} _{q},\quad f_{m}\neq 0.

Здесь $m$ — целое неотрицательное число, называемое степенью многочлена $f(x)$ , а $x^{k},k\in \mathbb {N} _{0}$ — элементы алгебры над $\mathbb {F} _{q},$ умножение которых задаётся правилами:

x^{k}\cdot x^{m}=x^{k+m},

x^{0}\equiv 1.

Такое определение позволяет умножать многочлены формально, не заботясь о том, что разные степени одного и того же элемента конечного поля могут совпадать^[1]^[2].

Любую функцию над конечным полем можно задать с помощью некоторого многочлена (например, интерполяционного многочлена Лагранжа).

Связанные определения

Число $m\geqslant 0$ называется степенью полинома и обозначается как $\deg(f(x))$ ^[2].
Если $f_{m}=1$ , то полином называется нормированным (приведённым)^[2]. Полином всегда можно нормировать делением его на коэффициент $f_{m}$ при старшей степени.
Сумма и произведение полиномов определены обычным образом, а операции с коэффициентами осуществляются в поле $\mathbb {F} _{q}$ .
Для двух полиномов $f(x)$ $f(x)$ и $h(x)\neq 0$ $h(x)\neq 0$ всегда найдутся полиномы $t(x)$ $t(x)$ и $r(x)$ $r(x)$ над полем $\mathbb {F} _{q}$ $\mathbb {F} _{q}$ , что будет выполняться соотношение
$f(x)=t(x)h(x)+r(x).$
- Если степень $r(x)$ строго меньше степени $h(x)$ , то такое соотношение называется представлением полинома $f(x)$ в виде частного и остатка от деления $f(x)$ на $h(x)$ , причем такое представление единственно^[3]. Ясно, что $f(x)-r(x)$ делится без остатка на $h(x)$ , что записывается как $f(x)\equiv r(x){\pmod {h(x)}}$ ^[4].
- Если $r(x)=0$ , то полином $h(x)$ называется делителем полинома $f(x)$ ^[5].
Полином является неприводимым над полем $\mathbb {F} _{q}$ , если он не имеет нетривиальных делителей (степени большей 0 и меньшей $\deg(f(x))$ )^[5]^[6].
Расширением поля $GF(q)$ называется множество $F[x]_{/(p(x))}$ классов вычетов по модулю неприводимого многочлена $p(x)$ над полем $GF(q)$ ^[6].
Минимальным многочленом (минимальной функцией) для элемента $\beta$ из расширенного поля называется такой нормированный многочлен $m(x)$ над $GF(q)$ минимальной степени, что $m(\beta )=0$ ^[7]^[8].
Корнем многочлена называется всякий элемент поля, значение этого многочлена на котором равно нулю.
Сопряженными называются элементы поля, являющиеся корнями одного и того же неприводимого многочлена^[9].

Корни многочлена

Полином степени m имеет ровно m корней (с учётом кратности), принадлежащих некоторому расширенному полю $\mathbb {F} _{Q},\quad \mathbb {F} _{q}\subseteq \mathbb {F} _{Q}$ . Если $q=p^{s}$ , где $p$ — простое, то $Q=p^{S},\;S\geqslant s$ . Исходя из свойств конечных полей, любой элемент поля $\mathbb {F} _{Q}$ является корнем двучлена $x^{Q}-x$ :

x^{Q}-x=\prod _{\alpha \in \mathbb {F} _{Q}}{(x-\alpha )}

Таким образом, корни многочлена $f(x)$ также являются корнями двучлена $x^{Q}-x$ ^[10].

Справедливы теорема Безу и следствия из неё:

Остаток от деления $f(x)$ на $(x-a)$ равен $f(a)$ .

Если $x_{0}$ — корень $f(x)$ , то $(x-x_{0})$ делит $f(x)$ .

Если $x_{1},\;\ldots ,\;x_{m}$ суть корни $f(x)$ , то

f(x)=a(x-x_{1})(x-x_{2})\ldots (x-x_{m}).

Также справедливы следующие теоремы:

Теорема 1. Если $x_{0}$ — корень $f(x)$ , то $x_{0}^{q}$ — тоже корень $f(x)$ ^[11].

Теорема 2. Сопряженные элементы поля Галуа имеют один и тот же порядок^[9].

Циклотомический класс

Следствием Теоремы 1 может быть тот факт, что, если $\alpha \in \mathbb {F} _{Q}$ — корень полинома $f(x)$ над полем $\mathbb {F} _{q}$ , то и $\alpha ^{q},\;\alpha ^{q^{2}},\;\alpha ^{q^{3}},\;\ldots \in \mathbb {F} _{Q}$ являются его корнями.

Определение: циклотомическим классом над полем $\mathbb {F} _{q},\;q=p^{s}$ , порождённым некоторым элементом $\alpha \in \mathbb {F} _{Q},\;Q=p^{S}$ называется множество всех различных элементов $\mathbb {F} _{Q}$ , являющихся $q$ -ми степенями $\alpha$ ^[12].

Если $\alpha$ — примитивный элемент^[13] (такой элемент, что $\alpha ^{Q-1}=1$ и $\alpha ^{k}\neq 1$ при $0<k<Q-1$ ) поля $\mathbb {F} _{Q},\;Q=q^{m}$ , то циклотомический класс $C=\{\alpha ,\;\alpha ^{q},\;\alpha ^{q^{2}},\;\ldots ,\;\alpha ^{q^{m-1}}\}$ над полем $\mathbb {F} _{q}$ будет иметь ровно $m$ элементов.

Следует отметить, что любой элемент из циклотомического класса может порождать этот и только этот класс, а, следовательно, и принадлежать только ему.

Примеры циклотомических классов

Пример 1. Пусть $q=2$ , $Q=2^{3}=8$ и $\alpha$ — примитивный элемент поля $\mathbb {F} _{8}$ , то есть $\alpha ^{7}=1$ и $\alpha ^{i}\neq 1$ при $i<7$ . Учитывая также, что $\alpha ^{8}=\alpha$ , можно получить разложение всех ненулевых элементов поля $\mathbb {F} _{8}$ на три циклотомических класса над полем $\mathbb {F} _{2}$ :

{\begin{matrix}\{1\},\\\{\alpha ,\;\alpha ^{2},\;\alpha ^{4}\},\\\{\alpha ^{3},\;\alpha ^{6},\;\alpha ^{5}\}.\end{matrix}}

Пример 2. Аналогично можно построить классы на поле $\mathbb {F} _{16}$ над полем $\mathbb {F} _{4}$ , то есть $q=4,\;Q=q^{2}=16$ . Пусть $\alpha$ — примитивный элемент поля $\mathbb {F} _{16}$ , значит $\alpha ^{15}=1,\;\alpha ^{16}=\alpha$ .

{\begin{matrix}\{1\},\\\{\alpha ,\;\alpha ^{4}\},\;\{\alpha ^{2},\;\alpha ^{8}\},\\\{\alpha ^{3},\;\alpha ^{12}\},\;\{\alpha ^{5}\},\;\{\alpha ^{10}\},\\\{\alpha ^{6},\;\alpha ^{9}\},\;\{\alpha ^{7},\;\alpha ^{13}\},\\\{\alpha ^{11},\;\alpha ^{14}\}.\end{matrix}}

Связь с корнями полиномов

Следующая Теорема устанавливает связь между циклотомическими классами и разложением полинома $x^{Q-1}-1$ на неприводимые полиномы над полем $\mathbb {F} _{q}$ .

Теорема 3. Пусть $\alpha ,\;\alpha ^{q},\;\alpha ^{q^{2}},\;\ldots ,\;\alpha ^{q^{m-1}}$ циклотомический класс, порожденный элементом $\alpha \in \mathbb {F} _{q^{l}}$ и полином $f(x)=f_{0}+f_{1}x+f_{2}x^{2}+\ldots +f_{m-1}x^{m-1}+x^{m}$ имеет в качестве своих корней элементы этого циклотомического класса, то есть

f(x)=(x-\alpha )(x-\alpha ^{q})\ldots (x-\alpha ^{q^{m-1}}).

Тогда коэффициенты $f_{0},\;f_{1},\;\ldots ,\;f_{m-1}$ полинома $f(x)$ лежат в поле $\mathbb {F} _{q}$ , а сам полином является неприводимым над этим полем.

Можно установить такое следствие из Теоремы 3. Из свойства конечных полей, говорящего о том, что все ненулевые элементы поля $\mathbb {F} _{Q}$ являются корнями многочлена $x^{Q-1}-1$ , можно заключить, что многочлен $x^{Q-1}-1$ можно разложить на неприводимые над полем $\mathbb {F} _{q}$ многочлены $f_{0}(x),\;f_{1}(x),\;\ldots ,\;f_{d}$ , каждый из которых соответствует своему циклотомическому классу^[14].

Виды многочленов

Примитивные многочлены

Определение. Порядок корней неприводимого многочлена называется показателем, к которому этот многочлен принадлежит. Неприводимый многочлен называется примитивным, если все его корни являются порождающими элементами мультипликативной группы поля^[15].

Все корни примитивного многочлена имеют порядок, равный порядку мультипликативной группы расширенного поля $\mathbb {F} _{Q}$ , то есть $Q-1$ ^[11].

Круговые многочлены

Пусть $\alpha$ есть порождающий элемент мультипликативной группы поля $GF(q^{m})$ , и её порядок равен $n=q^{m}-1$ , то есть $\alpha ^{q^{m}-1}=1$ . Пусть все элементы порядка $d$ являются корнями многочлена $\psi _{d}(x),\;n\,\vdots \,d$ . Тогда такой многочлен называется круговым и верно равенство^[16]:

x^{q^{m}-1}-1=\prod _{d\,\mid \,q^{m}-1}\psi _{d}(x)

Многочлены Жегалкина

Среди многочленов над конечными полями особо выделяют многочлены Жегалкина. Они представляют собой полиномы многих переменных над полем $GF(2)$ ^[17].

f(x_{1},\;x_{2},\;\ldots ,\;x_{N})=a+\sum _{1\leqslant i\leqslant N}a_{i}x_{i}+\sum _{1\leqslant i<j\leqslant N}a_{i,j}x_{i}x_{j}+\sum _{1\leqslant i<j<k\leqslant N}a_{i,\;j,\;k}x_{i}x_{j}x_{k}+\ldots +a_{1,\;2,\;\ldots ,\;N}x_{1}x_{2}\ldots x_{N}

С помощью такого полинома можно задать любую булеву функцию^[18] $f(x_{1},\;x_{2},\;\ldots ,\;x_{N})$ , причем единственным образом^[17]^[19].

Применение

Существует множество алгоритмов, использующих многочлены над конечными полями и кольцами.

Также многочлены над конечными полями используются в современном помехоустойчивом кодировании^[20] (для описания циклических кодов^[21] и для декодирования кода Рида — Соломона с помощью алгоритма Евклида^[22]), генераторах псевдослучайных чисел^[23] (реализуются при помощи регистров сдвига)^[24], поточном шифровании^[25] и алгоритмах проверки целостности данных.

См. также

Примечания

↑ Акритас, 1994, с. 146.
↑ ¹ ² ³ Блейхут, 1986, с. 88.
↑ Блейхут, 1986, с. 90.
↑ Блейхут, 1986, с. 91.
↑ ¹ ² Блейхут, 1986, с. 89.
↑ ¹ ² Сагалович, 2014, с. 79.
↑ Сагалович, 2014, с. 93.
↑ Блейхут, 1986, с. 104.
↑ ¹ ² Сагалович, 2014, с. 101.
↑ Сагалович, 2014, с. 82.
↑ ¹ ² Сагалович, 2014, с. 96.
↑ Сагалович, 2014, с. 105.
↑ Блейхут, 1986, с. 99.
↑ Сагалович, 2014, с. 97.
↑ Блейхут, 1986, с. 103.
↑ Сагалович, 2014, с. 102.
↑ ¹ ² Яблонский, 1986, с. 32.
↑ Яблонский, 1986, с. 12.
↑ Габидулин, Кшевецкий, Колыбельников, 2011, с. 81.
↑ Сагалович, 2014, с. 169—172.
↑ Блейхут, 1986, с. 116—121.
↑ Блейхут, 1986, с. 223—228.
↑ Габидулин, Кшевецкий, Колыбельников, 2011, с. 77—83.
↑ Алферов, Зубов, Кузьмин и др., 2005, с. 251—260.
↑ Габидулин, Кшевецкий, Колыбельников, 2011, с. 74—83.

Литература

Акритас А. Основы компьютерной алгебры с приложениями / пер. с англ. Е. В. Панкратьева. — М.: Мир, 1994. — 544 с.
Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии: Учебное пособие — 3-е изд., испр. и доп. — М.: Гелиос АРВ, 2005. — 480 с. — ISBN 978-5-85438-137-6
Блейхут Р. Э. Теория и практика кодов, контролирующих ошибки / под ред. К. Ш. Зигангирова, пер. пер. с англ. И.И.Грушко, В. М. Блиновского — М.: Мир, 1986. — 576 с.
Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
Сагалович Ю. Л. Введение в алгебраические коды — 3-е изд., перераб. и доп. — М.: ИППИ РАН, 2014. — 310 с. — ISBN 978-5-901158-24-1
Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вузов — 2-е изд., перераб. и доп. — М.: Наука, 1986. — 384 с.
Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.

[_194b344bce494665-1] Акритас, 1994, с. 146.

[_753325bfb512e3fe-2] ¹ ² ³ Блейхут, 1986, с. 88.

[_753326bfb512e549-3] Блейхут, 1986, с. 90.

[_753326bfb512e548-4] Блейхут, 1986, с. 91.

[_753325bfb512e3ff-5] ¹ ² Блейхут, 1986, с. 89.

[_0969f51995f6bddb-6] ¹ ² Сагалович, 2014, с. 79.

[_0969f71995f6c17b-7] Сагалович, 2014, с. 93.

[_38eb90c0af332127-8] Блейхут, 1986, с. 104.

[_f5b4c879d23302b1-9] ¹ ² Сагалович, 2014, с. 101.

[_0969f81995f6c2c9-10] Сагалович, 2014, с. 82.

[_0969f71995f6c17e-11] ¹ ² Сагалович, 2014, с. 96.

[_f5b4c879d23302b5-12] Сагалович, 2014, с. 105.

[_753326bfb512e540-13] Блейхут, 1986, с. 99.

[_0969f71995f6c17f-14] Сагалович, 2014, с. 97.

[_38eb90c0af332120-15] Блейхут, 1986, с. 103.

[_f5b4c879d23302b2-16] Сагалович, 2014, с. 102.

[_983607084ebbf43b-17] ¹ ² Яблонский, 1986, с. 32.

[_983605084ebbf091-18] Яблонский, 1986, с. 12.

[_41573a8174d4d05f-19] Габидулин, Кшевецкий, Колыбельников, 2011, с. 81.

[_8ca4373fce3d958b-20] Сагалович, 2014, с. 169—172.

[_db78abbef20e0dee-21] Блейхут, 1986, с. 116—121.

[_071c8385b9e130b3-22] Блейхут, 1986, с. 223—228.

[_cb800f78128d77e5-23] Габидулин, Кшевецкий, Колыбельников, 2011, с. 77—83.

[_fb59ab1e2aa6539c-24] Алферов, Зубов, Кузьмин и др., 2005, с. 251—260.

[_9c5cd6e6e50b742c-25] Габидулин, Кшевецкий, Колыбельников, 2011, с. 74—83.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

Многочлен над конечным полем

Содержание

Связанные определения

Корни многочлена